# boston-key-party-2016 bob's hat (layer 3)
# if q or p is small, then it's easy to factorize n

import gmpy2
import sys
n = 0xBAD20CF97ED5042DF696CE4DF3E5A678CF4FB3693D3DF12DFE9FD3FD8CC8AAB8B95533E414E3FC0C377F4EE54827118B1D30561A3C741BEA7C76899789B51743E076092DF9EB05DC97EB1505CE9EB12B5AB9E10ABF56F920A58E7E00ECF05977E872834DD8584CF4AC87CB7DC50159BD962C75CBEFB6C6AC3A31A74E7D8F1E4C10D5
n = 0x80FAB241E21AACBB5A0C0C58CE7D8A3F844F3F76C2B1006278D79CDD333550AB5F5F86425FDBF06063481D7D7922F1C17083532285B1D8FAEE843D8A02E74F277A47084BC5585F0D16A2AB7F2E2C074A274C9B890B05A4ED05739F9BAEAA501C265D68C04C146A5DAED6EF5E0A45AA7C9AE1E7C3741C39F7F00936D1D627BC5B
#n = int(sys.argv[1], 16)

prime = 1
while True:
  prime = gmpy2.next_prime(prime)
  if n % prime == 0:
    break

p = prime
q = n / p

print 'found small factor'

print 'p = %d' % p
print 'q = %d' % q
print '''generate private key with:
python ~/tools/crypto/rsatool/rsatool.py -p %s -q %s -o /tmp/privkey.pem''' % (p, q)

